import datetime
import math
import random
import unittest
from itertools import chain

import genetic


def get_fitness(genes, Graph):
    fitness = get_distance(Graph,genes[0],genes[1])
    length = len(genes)
    if length == 2:
        return fitness
    for i in range(int(length/2) - 1):
        start = genes[(i + 1) * 2]
        end = genes[(i + 1)*2 + 1]
        fitness += get_distance(Graph, start, end)

    return Fitness(round(fitness, 2))


def display(candidate, startTime):
    timeDiff = datetime.datetime.now() - startTime
    #print("{}\t{}\t{}\t{}".format(
    #    ' '.join(map(str, candidate.Genes)),
    #    candidate.Fitness,
    #    candidate.Strategy.name,
    #    timeDiff))

def get_distance(Graph,VertexA, VertexB):
    return Graph[VertexA][VertexB]


def mutate(genes, fnGetFitness):
    count = random.randint(2, len(genes))
    initialFitness = fnGetFitness(genes)
    while count > 0:
        count -= 1
        indexA, indexB = random.sample(range(len(genes)), 2)
        genes[indexA], genes[indexB] = genes[indexB], genes[indexA]
        fitness = fnGetFitness(genes)
        if fitness > initialFitness:
            return


def crossover(parentGenes, donorGenes, fnGetFitness):
    pairs = {Pair(donorGenes[0], donorGenes[-1]): 0}

    for i in range(len(donorGenes) - 1):
        pairs[Pair(donorGenes[i], donorGenes[i + 1])] = 0

    tempGenes = parentGenes[:]
    if Pair(parentGenes[0], parentGenes[-1]) in pairs:
        # find a discontinuity
        found = False
        for i in range(len(parentGenes) - 1):
            if Pair(parentGenes[i], parentGenes[i + 1]) in pairs:
                continue
            tempGenes = parentGenes[i + 1:] + parentGenes[:i + 1]
            found = True
            break
        if not found:
            return None

    runs = [[tempGenes[0]]]
    for i in range(len(tempGenes) - 1):
        if Pair(tempGenes[i], tempGenes[i + 1]) in pairs:
            runs[-1].append(tempGenes[i + 1])
            continue
        runs.append([tempGenes[i + 1]])

    initialFitness = fnGetFitness(parentGenes)
    count = random.randint(2, 20)
    runIndexes = range(len(runs))
    while count > 0:
        count -= 1
        for i in runIndexes:
            if len(runs[i]) == 1:
                continue
            if random.randint(0, len(runs)) == 0:
                runs[i] = [n for n in reversed(runs[i])]

        indexA, indexB = random.sample(runIndexes, 2)
        runs[indexA], runs[indexB] = runs[indexB], runs[indexA]
        childGenes = list(chain.from_iterable(runs))
        if fnGetFitness(childGenes) > initialFitness:
            return childGenes
    return childGenes

class Scavenger():
    def __init__(self,Graph,optimalSequence):
        self.Graph = Graph
        self.optimalSequence = optimalSequence
    #def test_8_queens(self):
    #    Graph = [
    #                [10, 3, 18, 11, 9, 28, 18, 32, 51, 49, 60],
    #                [7, 10, 25, 9, 6, 26, 15, 30, 49, 47, 58],
    #                [31, 26, 49, 22, 32, 39, 34, 43, 62, 60, 71],
    #                [10, 4, 28, 13, 10, 17, 12, 21, 40, 38, 49],
    #                [23, 16, 41, 25, 22, 23, 9, 27, 46, 44, 55],
    #                [29, 23, 47, 19, 11, 20, 7, 4, 23, 21, 32],
    #                [28, 21, 46, 30, 22, 15, 22, 19, 38, 36, 47],
    #                [45, 39, 63, 35, 27, 16, 23, 20, 19, 17, 28],
    #                [67, 61, 85, 57, 49, 38, 45, 22, 21, 19, 30],
    #                [48, 42, 66, 38, 30, 19, 26, 3, 2, 20, 11],
    #                [57, 51, 75, 47, 39, 28, 35, 12, 11, 9, 20]
    #            ]
    #    optimalSequence = [0, 3, 4, 8, 9, 10]
    #    self.solve(Graph, optimalSequence)

    def solve(self, Graph, optimalSequence):
        geneset = [i for i in optimalSequence]

        def fnCreate():
            return random.sample(geneset, len(geneset))

        def fnDisplay(candidate):
            display(candidate, startTime)

        def fnGetFitness(genes):
            return get_fitness(genes, Graph)

        def fnMutate(genes):
            mutate(genes, fnGetFitness)

        def fnCrossover(parent, donor):
            return crossover(parent, donor, fnGetFitness)

        #optimalFitness = fnGetFitness(optimalSequence)
        optimalFitness = Fitness(15000.0)
        startTime = datetime.datetime.now()
        best = genetic.get_best(fnGetFitness, None, optimalFitness, None,
                                fnDisplay, fnMutate, fnCreate, maxAge=500,
                                poolSize=25, crossover=fnCrossover)
        return best.Genes
        #self.assertTrue(not optimalFitness > best.Fitness)

class Fitness:
    def __init__(self, totalDistance):
        self.TotalDistance = totalDistance

    def __gt__(self, other):
        return self.TotalDistance < other.TotalDistance

    def __str__(self):
        return "{:0.2f}".format(self.TotalDistance)

class Pair:
    def __init__(self, node, adjacent):
        if node < adjacent:
            node, adjacent = adjacent, node
        self.Node = node
        self.Adjacent = adjacent

    def __eq__(self, other):
        return self.Node == other.Node and self.Adjacent == other.Adjacent

    def __hash__(self):
        return hash(self.Node) * 397 ^ hash(self.Adjacent)

#if __name__ == '__main__':
#    Graph = [
#             [10, 3, 18, 11, 9, 28, 18, 32, 51, 49, 60],
#             [7, 10, 25, 9, 6, 26, 15, 30, 49, 47, 58],
#             [31, 26, 49, 22, 32, 39, 34, 43, 62, 60, 71],
#             [10, 4, 28, 13, 10, 17, 12, 21, 40, 38, 49],
#             [23, 16, 41, 25, 22, 23, 9, 27, 46, 44, 55],
#             [29, 23, 47, 19, 11, 20, 7, 4, 23, 21, 32],
#             [28, 21, 46, 30, 22, 15, 22, 19, 38, 36, 47],
#             [45, 39, 63, 35, 27, 16, 23, 20, 19, 17, 28],
#             [67, 61, 85, 57, 49, 38, 45, 22, 21, 19, 30],
#             [48, 42, 66, 38, 30, 19, 26, 3, 2, 20, 11],
#             [57, 51, 75, 47, 39, 28, 35, 12, 11, 9, 20]
#         ]
#    optimalSequence = [0, 3, 4, 8, 9, 10]
#    a = Scavenger(Graph,optimalSequence)
#    b = a.solve(Graph,optimalSequence)
#    print(b)
